package leetcode

//https://leetcode.com/problems/combinations/

fun main(args: Array<String>) {
    println(combine(4, 2))
}


fun combine(n: Int, k: Int): List<List<Int>> {
    //参照 47题的思路，同样适用深度遍历，输出达到k长度即可
    val result = arrayListOf<List<Int>>()
    combineRecursive(n, arrayListOf(), k, result)
    return result
}

fun combineRecursive(n: Int, tmp: ArrayList<Int>, k: Int, result: ArrayList<List<Int>>) {
    if (tmp.size == k) {
        result.add(ArrayList(tmp))
    } else {
        for (i in 1 until n + 1) {
            //去除重复组合，强制排列是升序，用这个约束来达到去重的效果
            if (tmp.contains(i) || (tmp.isNotEmpty() && i < tmp.last())) continue
            tmp.add(i)
            combineRecursive(n, tmp, k, result)
            tmp.removeAt(tmp.lastIndex)//下一层的for循环完了之后，需要确定本层循环的下一个数，所以弹出末尾的数字放置新数
        }
    }
}